/*
658. 找到 K 个最接近的元素
https://leetcode.cn/problems/find-k-closest-elements/description/?envType=problem-list-v2&envId=binary-search
难度：中等  李佳韵  2024/09/01
二分查找
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    // 找到与给定值 x 最接近的 k 个元素
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        vector<int> result;
        // 存储元素与 x 的差值以及元素本身
        vector<pair<int, int>> value;
        int n = arr.size();
        // 计算每个元素与 x 的差值，并将差值和元素组成 pair 存入 value 中
        for (int i = 0; i < arr.size(); ++i) {
            value.push_back({abs(arr[i] - x), arr[i]});
        }
        // 按照差值从小到大排序 value
        sort(value.begin(), value.end());
        // 取前 k 个元素存入 result
        for (int i = 0; i < k; ++i) {
            result.push_back(value[i].second);
        }
        // 对 result 中的元素进行升序排序
        sort(result.begin(), result.end());
        return result;
    }
};

int main() {
    cout << "请输入数组元素个数：";
    int n;
    cin >> n;
    vector<int> arr;
    cout << "请输入数组元素：";
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        arr.push_back(num);
    }
    cout << "请输入要找的最接近元素的个数 k：";
    int k;
    cin >> k;
    cout << "请输入目标值 x：";
    int x;
    cin >> x;
    Solution solution;
    vector<int> result = solution.findClosestElements(arr, k, x);
    cout << "与 " << x << " 最接近的 " << k << " 个元素为：";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}